package com.yuren.codecrushlearn.Q5300;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 * N皇后问题
 * @author 10204
 * @date 2025-05-27 00:59
 */
public class Q5391 {
    int count = 0;

    public int solveNQueues(int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; ++j) {
                sb.append('.');
            }
            board.add(sb.toString());
        }

        recur(board, 0);
        return count;
    }

    private void recur(List<String> board, int step) {
        if (step == board.size()) {
            count++;
            return;
        }

        for (int j = 0; j < board.size(); ++j) {
            if (check(board, step, j)) {
                StringBuilder sb = new StringBuilder(board.get(step));
                sb.setCharAt(j, 'Q');
                board.set(step, sb.toString());
                recur(board, step + 1);
                sb.setCharAt(j, '.');
                board.set(step, sb.toString());
            }
        }
    }

    private boolean check(List<String> board, int row, int col) {
        // Check column
        for (int i = 0; i < row; ++i) {
            if (board.get(i).charAt(col) == 'Q') return false;
        }

        // Check top left to bottom right
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board.get(i).charAt(j) == 'Q') return false;
        }

        // Check bottom left to top right
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); --i, ++j) {
            if (board.get(i).charAt(j) == 'Q') return false;
        }

        return true;
    }
}
